//贪心做法：
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int x1=0x3f3f3f3f;
        int x2=0x3f3f3f3f;
        int y1=0x3f3f3f3f;
        int y2=0x3f3f3f3f;
        int sum=0;
        for(auto&ch:nums)
        {   
            sum+=ch;
            if(ch%3==1)
            {
                if(ch<x1)
                {
                x2=x1;
                x1=ch;
                }
                else if(ch>=x1&&ch<=x2)
                {
                    x2=ch;
                }
            }
            else if(ch%3==2)
            {
                if(ch<y1)
                {
                    y2=y1;
                    y1=ch;
                }
                else if(ch>=y1&&ch<=y2)
                {
                    y2=ch;
                }
            }
            
        }
        if(sum%3==0) return sum;
        else if(sum%3==1) return max(sum-x1,sum-y1-y2);
        else return max(sum-y1,sum-x1-x2);
    }
};

//动态规划解法

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) 
    {
       int n=nums.size();
       vector<vector<int>>dp(n+1,vector<int>(3,-1));
       dp[0][0]=0;
       for(int i=1;i<=n;i++)
       {
         int remainder = nums[i-1] % 3;
        for(int j=0;j<3;j++)
        {
            dp[i][j]=dp[i-1][j];
            int prev_state = (j - remainder + 3) % 3;
            if(dp[i-1][prev_state]!=-1)
            dp[i][j] = max(dp[i][j], dp[i-1][prev_state] + nums[i-1]);
                
        }
       }
       return dp[n][0];
    }
};